#!/usr/bin/env python
from sys import argv, exit
from random import randint as rand, shuffle



class Chromosome(object):
	def __init__(self,data):
		self.positions = data
		self.N = len(data)
		self.nConflicts = 0
		self.conflicts = [0 for i in xrange(self.N)]
		
		for i in xrange(self.N):
			self.positions[i] = int(self.positions[i])
			
		
	def __str__(self):
		matrix = [[' ' for j in xrange(self.N)] for i in xrange(self.N)]
		
		for col in xrange(self.N):
			matrix[int(self.positions[col])][col] = 'X'
		
		sMatrix = ''
		for line in matrix:
			sMatrix += str(line)
			sMatrix += "\n"
		
		return sMatrix
		
	def Conflicts(self):
		self.nConflicts = 0
		
		# Loop through each queen
		diag1 = 0
		diag2 = 0
		straight = 0
		#print 'new'
		for i in xrange(self.N):
			
			# Validate each possible conflicts
			# Diagonal, right-top
			k = 1
			pos = self.positions[i]
			
			for j in range(i+1, self.N):
				if (self.positions[j]) == pos - k:
					self.conflicts[i] += 1
					self.nConflicts += 1
				k += 1
			
			# Diagonal, left-bottom
			k = 1
			for j in range(i-1,0-1,-1):
				if (self.positions[j]) == pos + k:
					self.conflicts[i] += 1
					self.nConflicts += 1
				k += 1	
				
			# Diagonal, left-top
			k = 1
			pos = self.positions[i]
			for j in range(i-1,0-1,-1):
				if (self.positions[j]) == pos - k:
					self.conflicts[i] += 1
					self.nConflicts += 1
				k += 1
			
			# Diagonal, right-bottom
			k = 1
			for j in range(i+1, self.N):
				if (self.positions[j]) == pos + k:
					self.conflicts[i] += 1
					self.nConflicts += 1
				k += 1	
			
			# Line, left-right
			for j in xrange(self.N):
				if self.positions[j] == pos and (j != i):
					#print 'I: ' + str(i)
					#print 'J: ' + str(j)
					self.conflicts[i] += 1
					self.nConflicts += 1
	
class Population(object):
	def __init__(self, option, probe=False):
		
		self.rep = 2
		self.mut = 2
		self.fittest = None
		
		if probe == True:
			self.rep = int(raw_input("Reproduction scheme\n1. 1 Slice\n2. 2 Slice\n> "))
			self.mut = int(raw_input("Mutation schema\n1. 2-opt\n2. Same Line\n> "))
		
		if option != 'random':
			try:
				f = open(option, 'r')
			except:
				raise
				
			self.P = int(f.readline().strip())
			self.N = int(f.readline().strip())
			self.chromosomes = []
			self.chromoChildren = []
			
			for n in xrange(self.P):
				tmp = Chromosome(((f.readline()).strip()).split(' '))
				self.chromosomes.append(tmp)
				
	def __iter__(self):
		return self.chromosomes.__iter__()
		
	def __str__(self):
		data = ''
		for C in self.__iter__():
			data += str(C)
			data += "\n"
		
		return data
		
	def Conflicts(self):
		if self.chromosomes == []:
			return 
		for C in self.chromosomes:
			C.Conflicts()
	
	def Reproduce(self):
		N = len(self.chromosomes)
		# Match Chromosomes two by two
		
		shuffle(self.chromosomes)
		if N % 2 == 1:
			self.chromoChildren.append(self.chromosomes.pop())
		
		pairs = zip(self.chromosomes[0:N/2], self.chromosomes[N/2:])
		
		
		# 1 Slice rep
		if self.rep == 1:
			alpha = (self.N * 2)/3
			# loop through the pairs
			for pair in pairs:
				p = rand(0,self.N)
				if p < alpha:
					#print 'test'
					c1 = pair[0].positions[0:p] + pair[1].positions[p:]
					c2 = pair[1].positions[0:p] + pair[0].positions[p:]
					self.chromoChildren.append(Chromosome(c1))
					self.chromoChildren.append(Chromosome(c2))
				else:
					self.chromoChildren.append(pair[0])
					self.chromoChildren.append(pair[1])
		
		# 2 Slice rep			
		elif self.rep == 2:
			alpha = (self.N * 2) /3
			for pair in pairs:
				p = rand(0,self.N)
				if p < alpha:
					s1 = p
					s2 = s1
					
					while s1 == s2:
						s2 = rand(0,self.N)
						
					if s1 > s2:
						t = s1
						s1 = s2
						s2 = t
						
					c1 = pair[0].positions[0:s1] + pair[1].positions[s1:s2] + pair[0].positions[s2:]
					c2 = pair[1].positions[0:s1] + pair[0].positions[s1:s2] + pair[1].positions[s2:]
					
					self.chromoChildren.append(Chromosome(c1))
					
					self.chromoChildren.append(Chromosome(c2))
					
				else:
					self.chromoChildren.append(pair[0])
					self.chromoChildren.append(pair[1])
					
					
		
		
	def Mutate(self):
		
		N = len(self.chromoChildren)
		shuffle(self.chromoChildren)
		self.pool = []
		
		pairs = zip(self.chromoChildren[0:N/2], self.chromoChildren[N/2:]) 
		
		if self.mut == 1:
			beta = 20
			for pair in pairs:
				if rand(0,100) < beta:
					s1 = rand(0, len(pair[0].positions)-1)
					#print s1
					#print len(pair[0].positions)
					tmp = pair[0].positions[s1]
					pair[0].positions[s1] = pair[1].positions[s1]
					pair[1].positions[s1] = tmp
				self.pool.append(pair[0])
				self.pool.append(pair[1])
		
		# Broken		
		elif self.mut == 2:
			
			for c in self.chromoChildren:
				n = len(c.positions)
				rows = [[] for i in xrange(n)]
				for i in xrange(n):
					rows[c.positions[i]].append(i)
				
				for i in xrange(n):
					if rows[i] == []:
						for j in xrange(n):
							if len(rows[j]) > 1:
								idx = rows[j].pop()
								rows[i].append(idx)
								
								c.positions[idx] = i
				
								
								break
				#print 'Pos: ' + str(c.positions)
				self.pool.append(c)
				
				#print str(rows)
				
				
		self.pool += self.chromosomes
		
	def MurderSpree(self):
		self.chromosomes = []
		self.chromoChildren = []
		
		shuffle(self.pool)
		N = len(self.pool)
		
		if N %2 == 1:
			self.chromosomes.append(self.pool.pop())
		
		pairs = zip(self.pool[0:N/2], self.pool[N/2:]) 
		
		for pair in pairs:
			pair[0].Conflicts()
			pair[1].Conflicts()
			
			if pair[0].nConflicts >= pair[1].nConflicts:
				self.chromosomes.append(pair[1])
			else:
				self.chromosomes.append(pair[0])
				
	def Fittest(self):
		if self.fittest == None:
			score = float('inf')
		else:
			score = self.fittest.nConflicts
		
		for c in self.chromosomes:
			c.Conflicts()
			if score > c.nConflicts:
				score = c.nConflicts
				self.fittest = c
			

			

if __name__ == "__main__":
	generation = 5
	test = False
	

		
	
	try:
		pop = Population('/home/vezril/ELE440/ELE440/lab4/N8/P50N8.txt', probe=True)
	except:
		print 'Unable to open file'
		exit(-1)
	
	
	''' TEST MODE START '''
	if test == True:
		'''
		pop.chromosomes[2].Conflicts()
		print pop.chromosomes[2].positions
		print pop.chromosomes[2].conflicts
		print pop.chromosomes[2]
		print pop.chromosomes[2].nConflicts
		exit(0)
		'''
		
		print 'old'
		
		for c in pop:
			print c.positions
			
		print 'new'
		
		pop.Reproduce()
		for c in pop.chromoChildren:
			print c.positions
		
	''' TEST MODE END'''
	
	cnt  = 0
	#pop.Conflicts()
	for G in xrange(int(raw_input("Number of generations> "))):
		print 'Generation ' + str(G)
		
		pop.Reproduce()
		pop.Mutate()
		pop.MurderSpree()
		pop.Conflicts()
		pop.Fittest()
		print pop.fittest.positions
		print pop.fittest.nConflicts
			

